-------<br />METRIC 2011 Trimester at Institut Henri Poincaré (Paris, France, Jan-Mar 2011)<br />-------<br />Workshop on Metric embeddings, algorithms and hardness of approximation<br />January 17-21, 2011<br />-------<br />Jan 20, 9:00-10:00<br />Per Austrin (U. Toronto)<br />Approximability of Minimum Distance of Codes<br />-------<br />The focus of this talk is the problem of computing the minimum distance<br />of a linear code. This problem is NP-hard, and we give an overview of<br />what is known about the approximability of this problem. We also<br />describe a new, elementary proof of NP-hardness of approximation for the<br />problem (joint work with Subhash Khot).
